package primalgorithms.dynamicplanning;

import java.util.HashMap;

public class _04Rob {
    public static int rob(int[] nums) {
        return robHelper(nums,nums.length-1,new HashMap<Integer,Integer>());
    }

    private static int robHelper(int[] nums, int i,HashMap<Integer,Integer> map) {
        //递归终止条件：没有家可以偷了
        if (i < 0){
            return 0;
        }
        /** 运行之后我们发现直接超时，这是因为递归中包含大量的重复计算
        int last = robHelper(nums,i-1);
        int lastLast = robHelper(nums,i-2);
        int ifDo = lastLast + nums[i];
        return Math.max(last,ifDo);
        */
        //优化 ==> 之前算过就不用算第二次了
        int last = 0,lastLast = 0;
        if (map.containsKey(i - 2)){
            lastLast = map.get(i - 2);
        }else {
            lastLast = robHelper(nums,i - 2,map);
            map.put(i - 2,lastLast);
        }
        if (map.containsKey(i - 1)){
            last = map.get(i - 1);
        }else {
            last = robHelper(nums,i - 1,map);
            map.put(i - 1,last);
        }
        int ifDo = lastLast + nums[i];
        return Math.max(last,ifDo);
    }
}
